//
// Created by 86138 on 2025/7/9.
//

#include <iostream>
#include <vector>

using namespace std;

int fib(int n) {
    /* 1. 定义dp数组
       2. 写出递推公式
       3. 初始化dp数组
       4. 如何遍历dp数组
       5. 需要debug的话，打印dp数组

    */
    if (n < 2) return 1;
    vector<int> dp(n + 1);
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    for (auto x : dp) {
        cout << x << " ";
    }
    cout << endl;

    return dp[n];
//     int a, b, sum;
//     a = 0;
//     b = 1;
//     for (int i = 2; i <= n; i++) {
//         sum = a + b;
//         a = b;
//         b = sum;
//     }
//     return sum;
}

int main() {
    cout << fib(9) << endl;
    return 0;
}